#include <stdio.h>
#include <stdlib.h>

void print(int *A,int r)
{
	int i;
	for(i = 0;i<r;i++)
	{
		printf("%d ",A[i]);
	}
	printf("\n");
}

void merge(int *A ,int p, int q,int r)
{
	int n1 = q - p +1;
	int n2 = r - q;
	
	int *L = malloc(n1*sizeof(int));
	int *R = malloc(n2*sizeof(int));

	int i,j,k;
	for(i = 0;i < n1; i++)
	{
		L[i] = A[p+i];
	}

	for(j = 0;j < n2; j++)
	{
		R[j] = A[q+j+1];
	}

	i = j = 0;
	for(k=p; k<=r; k++)
	{
		if(i< n1 && j <n2)
		{
			if(L[i] <= R[j])
				A[k] = L[i++];
			else
				A[k] = R[j++];
		}
		else
		{
			while(i<n1)
				A[k++] = L[i++];
			
			while(j<n2)
				A[k++] = R[j++];
		}
	}
	free(L);
	free(R);
}


void merge_sort(int *A,int p,int r)
{
	int q;
	if(p<r)
	{
		q = (p+r)/2;
		merge_sort(A,p,q);
		merge_sort(A,q+1,r);
		merge(A,p,q,r);
	}
}